package th.retrofit.lib;

/**
 * 篮球（5V5）比赛中，每个球员拥有一个战斗力，每个队伍的所有球员战斗力之和为该队伍的总体战斗力。
 * 现有10个球员准备分为两队进行训练赛，教练希望2个队伍的战斗力差值能够尽可能的小，以达到最佳训练效果。
 * 给出10个球员的战斗力，如果你是教练，你该如何分队，才能达到最佳训练效果？请输出该分队方案下的最小战斗力差值。
 *
 * 输入描述:
 * 10个篮球队员的战斗力（整数，范围[1,10000]），战斗力之间用空格分隔，如：10 9 8 7 6 5 4 3 2 1
 * 不需要考虑异常输入的场景。
 * 输出描述:
 * 最小的战斗力差值，如：1
 * 示例1
 * 输入
 * 10 9 8 7 6 5 4 3 2 1
 * 输出
 * 1
 * 说明
 * 1 2 5 9 10分为一队，3 4 6 7 8分为一队，两队战斗力之差最小，输出差值1。
 * 备注：球员分队方案不唯一，但最小战斗力差值固定是1
 */
public class OtherSolution1 {

    /**
     * 抽象为长度为2n的数组，均分成两个长度为n的数组，使得两个长度为n的数组和之间的差值最小
     * @param arr 长度为2n
     * @return 最小差值
     */
    public int minDValue(int[] arr) {
        int length = arr.length >> 1;
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        int target = sum >> 1;
        // dp[i][j] 表示选择i个元素的和为j，能找到则为true，不能则为false
        boolean[][] dp = new boolean[length + 1][target + 1];
        dp[0][0] = true;
        for (int i = 1; i <= arr.length; i++) {
            for (int j = Math.min(i, length); j >= 1 ; j--) {
                for (int k = 1; k <= target ; k++) {
                    if (k >= arr[i - 1] && dp[j - 1][k - arr[i - 1]]) {
                        dp[j][k] = true;
                    }
                }
            }
        }
        for (int i = target; i >= 0; i--) {
            if (dp[length][i]) {
                return sum - 2 * i;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
//        int[] arr = new int[]{7, 3, 2, 1};
        System.out.println(new OtherSolution1().minDValue(arr));
    }

}
